package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 两个字符串的最小ASCII删除和
    static class Solution {
        public int minimumDeleteSum(String _s1, String _s2) {
            // 1) 边界处理
            char[] s1 = _s1.toCharArray();
            char[] s2 = _s2.toCharArray();
            int n = s1.length;
            int m = s2.length;

            // 2) dp[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 的公共子序列的最大 ASCII 和
            int[][] dp = new int[n + 1][m + 1];

            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    // 先考虑跳过 s1[i-1] 或跳过 s2[j-1]
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    // 如果当前字符相等，可以把这个字符加入公共子序列
                    if (s1[i - 1] == s2[j - 1]) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + s1[i - 1]);
                    }
                }
            }

            // 3) 计算两个字符串所有字符的 ASCII 总和
            int sum = 0;
            for (int i = 0; i < n; i++) {
                sum += s1[i];
            }
            for (int i = 0; i < m; i++) {
                sum += s2[i];
            }

            // 4) 答案 = 总和 - 2 * 最大公共子序列 ASCII 和
            return sum - 2 * dp[n][m];
        }
    }
}